栈 - 20. 有效的括号

Problem: 20. 有效的括号

思路

使用一个栈维护没有匹配的括号序列

解题过程

1. 向st里添加一个哨兵元素（比如说'#'），放置在栈底部（别问我为什么）

2. 如果遇到)、]、}，就观察栈顶，如果可以配对，就弹出配对的左括号，否则括号进栈

3. 如果这个字符不是右括号（即左括号），就进栈

4. 判断栈是否只有哨兵

代码

C++

xxxxxxxxxx
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.size();
        st.push('#');
        for (int i = 0; i < n; i++) {
            if (s[i] == ')') {
                if (st.top() == '(') {
                    st.pop();
                } else {
                    st.push(')');
                }
            } else if (s[i] == ']') {
                if (st.top() == '[') {
                    st.pop();
                } else {
                    st.push(']');
                }
            } else if (s[i] == '}') {
                if (st.top() == '{') {
                    st.pop();
                } else {
                    st.push('}');
                }
            } else {
                st.push(s[i]);
            }
        }
        return st.size() == 1;
    }
};

Python

xxxxxxxxxx
class Solution:
    def isValid(self, s: str) -> bool:
        st = [ '#' ]
        n = len(s)
        for i in range(n):
            if s[i] == ')':
                if st[-1] == '(':
                    st.pop()
                else:
                    st.append(')')
            elif s[i] == ']':
                if st[-1] == '[':
                    st.pop()
                else:
                    st.append(']')
            elif s[i]  == '}':
                if st[-1] == '{':
                    st.pop()
                else:
                    st.append('}')
            else:
                st.append(s[i])
        return len(st) == 1

C#

xxxxxxxxxx
public class Solution {
    public bool IsValid(string s) {
        Stack<char> st = new Stack<char>();
        int n = s.Length;
        st.Push('#');
        for (int i = 0; i < n; i++) {
            if (s[i] == ')') {
                if (st.Peek() == '(') {
                    st.Pop();
                } else {
                    st.Push(')');
                }
            } else if (s[i] == ']') {
                if (st.Peek() == '[') {
                    st.Pop();
                } else {
                    st.Push(']');
                }
            } else if (s[i] == '}') {
                if (st.Peek() == '{') {
                    st.Pop();
                } else {
                    st.Push('}');
                }
            } else {
                st.Push(s[i]);
            }
        }
        return st.Count == 1;
    }
}